Time based key-value store

Time: Set:O(1), Get:O(LogN); Space: O(N); medium

Create a timebased key-value store class TimeMap, that supports two operations.

  1. set(string key, string value, int timestamp)

  • Stores the key and value, along with the given timestamp.

  1. get(string key, int timestamp)

  • Returns a value such that set(key, value, timestamp_prev) was called previously, with timestamp_prev <= timestamp.

  • If there are multiple such values, it returns the one with the largest timestamp_prev.

  • If there are no values, it returns the empty string (“”).

Example 1:

Input/Output:

  • kv = TimeMap()

  • kv.set(“foo”, “bar”, 1) // store the key “foo” and value “bar” along with timestamp = 1

  • kv.get(“foo”, 1) -> “bar”

  • kv.get(“foo”, 3) -> “bar” since there is no value corresponding to foo at timestamp 3 and timestamp 2, then the only value is at timestamp 1 ie “bar”

  • kv.set(“foo”, “bar2”, 4);

  • kv.get(“foo”, 4) -> “bar2”

  • kv.get(“foo”, 5) -> “bar2”

Example 2:

Input/Output:

  • kv = TimeMap()

  • kv.set(“love”,“high”,10)

  • kv.set(“love”,“low”,20)

  • kv.get(“love”,5) -> “”

  • kv.get(“love”,10) -> “high”

  • kv.get(“love”,15) -> “high”

  • kv.get(“love”,20) -> “low”

  • kv.get(“love”,25) -> “low”

Constraints:

  • All key/value strings are lowercase.

  • All key/value strings have length in the range [1, 100]

  • The timestamps for all TimeMap.set operations are strictly increasing.

  • 1 <= timestamp <= 10^7

  • TimeMap.set and TimeMap.get functions will be called a total of 120000 times (combined) per test case.

1. Binary Search [O(1)..O(LogN), O(N)]

[1]:

import collections
import bisect

class TimeMap(object):
    """
    Time:  set: O(1)
           get: O(LogN)
    Space: O(NameError)
    """
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.lookup = collections.defaultdict(list)

    def set(self, key, value, timestamp):
        """
        Stores the key and value, along with the given timestamp.
        :type key: str
        :type value: str
        :type timestamp: int
        :rtype: None
        """
        self.lookup[key].append((timestamp, value))


    def get(self, key, timestamp):
        """
        Returns a value such that set(key, value, timestamp_prev) was called previously, with timestamp_prev <= timestamp.
        If there are multiple such values, it returns the one with the largest timestamp_prev.
        If there are no values, it returns the empty string ("").
        :type key: str
        :type timestamp: int
        :rtype: str
        """
        A = self.lookup.get(key, None)
        if A is None:
            return ''
        i = bisect.bisect_right(A, (timestamp+1, 0))

        return A[i-1][1] if i else ''

[3]:

kv = TimeMap()
kv.set("foo", "bar", 1); # store the key "foo" and value "bar" along with timestamp = 1
assert(kv.get("foo", 1)) == "bar"
assert(kv.get("foo", 3)) == "bar" # there is no value corresponding to foo at timestamp 3 and timestamp 2, then the only value is at timestamp 1 ("bar")
kv.set("foo", "bar2", 4)
assert(kv.get("foo", 4)) == "bar2"
assert(kv.get("foo", 5)) == "bar2"

kv = TimeMap()
kv.set("love", "high", 10)
kv.set("love", "low", 20)
assert(kv.get("love",5)) == ""
assert(kv.get("love",10)) ==  "high"
assert(kv.get("love",15)) == "high"
assert(kv.get("love",20)) == "low"
assert(kv.get("love",25)) == "low"